#include <iostream>

using namespace std;

int main()
{
	int T;
	cin >> T;
	
	while (T -- )
	{
		int n, m;
		cin >> n >> m;
		
		string a, b;
		
		cin >> a >> b;
		
		for (int i = 0; i < n; i ++ ) if (a[i] >= 'a') a[i] -= 32;
		for (int i = 0; i < m; i ++ ) if (b[i] >= 'a') b[i] -= 32;
		
//		cout << a << b << endl;

		int res = 0;

		for (int i = 0; i <= m - n; i ++ )
		{
			int t = i;
			int j = 0;
			
			while (j < n && b[t] == a[j]) j ++ , t ++ ;
			
			if (j == n) res ++ ;
		}
		
		cout << res << endl;
	}
	
	return 0;
}